
"""
NC19 连续子数组的最大和

https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=117&&tqId=37797&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型
#

from typing import List


class Solution:
    def method1(self, array: List[int]) -> int:
        """
        暴力解法: 通不过
        O(n^2)
        """
        size = len(array)

        res = -100  # 题目给定的数据值范围
        # [l...r]
        for l in range(size):
            for r in range(l+1, size + 1):
                res = max(sum(array[l:r]), res)

        return res

    def method2(self, array: List[int]) -> int:
        """
        预计算数组和:通不过
        O(n^2)
        """
        size = len(array)
        # sums[i]表示[0...i-1]的和，
        sums = [0] * (size + 1)

        for i in range(1, size + 1):
            sums[i] = sums[i-1] + array[i - 1]

        res = -100  # 题目给定的数据值范围
        for l in range(size):
            for r in range(l+1, size + 1):
                res = max(sums[r] - sums[l], res)

        return res

    def method3(self, array: List[int]) -> int:
        """
        动态规划

        step 1:可以用dp数组表示以下标i为终点的最大连续子数组和。
        step 2:遍历数组，每次遇到一个新的数组元素，连续的子数组要么加上变得更大，
            要么这个元素本身就更大，要么会更小，更小我们就舍弃，因此状态转移为
            dp[i]=max(dp[i-1]+array[i],array[i])。
        step 3:因为连续数组可能会断掉，每一段只能得到该段最大值，因此我们需要维护一个最大值。

        时间复杂度:O(n)
        空间复杂度:O(n)
        """
        size = len(array)

        # 记录到下标i为止的最大连续子数组和
        dp = [0 for i in range(size)]
        dp[0] = array[0]
        max_sum = dp[0]

        for i in range(1, size):
            # 状态转移：连续子数组和最大值
            dp[i] = max(dp[i-1]+array[i], array[i])
            # 维护最大值
            max_sum = max(max_sum, dp[i])

        return max_sum

    def method4(self, array: List[int]) -> int:
        """
        动态规划优化
        method3,动态规划在状态转移的时候只用到了i-1的信息,
        没有使用整个辅助数组的信息，因此可以将数组优化掉。

        时间复杂度:O(n)
        空间复杂度:O(1)
        """
        pre = array[0]  # 只要维护注，上一个子序列的最大和值即可
        max_sum = pre

        for i in range(1, len(array)):
            pre = max(pre+array[i], array[i])
            max_sum = max(pre, max_sum)

        return max_sum

    def FindGreatestSumOfSubArray(self, array: List[int]) -> int:
        # write code here
        assert len(array) > 0, "the array must have a item"
        return self.method4(array)


def test():
    obj = Solution()
    # arr = [1, -2, 3, 10, -4, 7, 2, -5]
    arr = [-1, -2, -3, -4, 5]
    res = obj.FindGreatestSumOfSubArray(arr)
    print(res)


if __name__ == "__main__":
    test()
